#include "MLClustering_KMeans.h"
_MYLABLIB_BEGIN

CMLClustering_KMeans::CMLClustering_KMeans(void)
{
}

CMLClustering_KMeans::~CMLClustering_KMeans(void)
{
}

int CMLClustering_KMeans::SetParameters(const std::wstring& wstrParams)
{
	// Get the K parameter
	int nRet = swscanf_s(wstrParams.c_str(),L"k=%d", &m_nK);
	if (nRet != 1)
	{
		ML_ASSERT(false);
		return -1;
	}
	return 0;
}

int CMLClustering_KMeans::DoClustering(const CMLDataSet& dataSet, std::vector<CMLDataCluster>& vClusters)
{
	int i,j;
	std::vector<std::vector<int>> lastClusters;
	std::vector<std::vector<int>> curClusters;

	// Random select data center
	m_vCenters.clear();

	RandomInitCenters(dataSet);
	// Clustering
	ConvergeAllPoints(dataSet, curClusters);
	while(IsClutersDifferent(curClusters, lastClusters))
	{
		// Re-calculate the means of clusters
		ResetCenters(dataSet, curClusters);
		// Record the current cluster results
		lastClusters = curClusters;
		curClusters.clear();
		// Cluster the dataset again
		ConvergeAllPoints(dataSet,curClusters);
	}
	
	// Copy result
	vClusters.clear();
	vClusters.resize(curClusters.size());
	for (i=0; i<(int)vClusters.size(); i++)
	{
		CMLDataCluster& cluster = vClusters[i];
		const std::vector<int>& vIndexes = curClusters[i];

		cluster.dataset.Resize((int)vIndexes.size());
		for (j=0; j<(int)vIndexes.size(); j++)
		{
			cluster.dataset.Set(j, dataSet.Get(vIndexes[j]));
		}
		cluster.center = m_vCenters[i];
	}
	return 0;
}

int CMLClustering_KMeans::DoClustering(const CMLDataSet& dataSet, const std::vector<double>& vWeights, 
										   std::vector<CMLDataCluster>& vClusters)
{
	std::vector<std::vector<int>> lastClusters;
	std::vector<std::vector<int>> curClusters;

	// Random select data center
	m_vCenters.clear();
	int nRet = RandomInitCenters(dataSet);
	ML_ON_FAILED_RETURN(nRet);
	
	// Clustering
	ConvergeAllPoints(dataSet, curClusters);
	while(IsClutersDifferent(curClusters, lastClusters))
	{
		// Re-calculate the means of clusters
		ResetCentersWithWeights(dataSet, vWeights, curClusters);
		// Record the current cluster results
		lastClusters = curClusters;
		curClusters.clear();
		// Cluster the dataset again
		ConvergeAllPoints(dataSet,curClusters);
	}
	
	// Copy result
	vClusters.clear();
	vClusters.resize(curClusters.size());
	int i,j;
	for (i=0; i<(int)vClusters.size(); i++)
	{
		CMLDataCluster& cluster = vClusters[i];
		const std::vector<int>& vIndexes = curClusters[i];

		cluster.dataset.Resize((int)vIndexes.size());
		for (j=0; j<(int)vIndexes.size(); j++)
		{
			cluster.dataset.Set(j, dataSet.Get(vIndexes[j]));
		}
		cluster.center = m_vCenters[i];
	}
	return 0;
}

int CMLClustering_KMeans::RandomInitCenters(const CMLDataSet& dataSet)
{
	int i;

	std::set<int> selectedIndexes;
	std::set<CMLDataPoint> setDatapoints;
	CMLDataSet uniqueDataSet;

	setDatapoints.clear();
	for (i=0; i<dataSet.Count(); i++)
		setDatapoints.insert(dataSet.Get(i));
	int nUniqueDataSize = (int)setDatapoints.size();
	if (nUniqueDataSize < m_nK)
	{
		std::wcerr << L"k-means : unique number "<< nUniqueDataSize << L" of data points is less than K="<< m_nK << L'\n';
		ML_ASSERT(false);
		return -1;
	}

	uniqueDataSet.Resize(nUniqueDataSize);
	std::set<CMLDataPoint>::const_iterator Iter = setDatapoints.begin();
	for (i=0; i<nUniqueDataSize; i++)
	{
		uniqueDataSet.Set(i, *Iter);
		Iter++;
	}

	m_vCenters.resize((size_t)m_nK);
	for (i=0; i<m_nK; i++)
	{
		int nDataIndex = rand() % nUniqueDataSize;
		while (selectedIndexes.find(nDataIndex) != selectedIndexes.end()) // avoid the duplicate index
			nDataIndex = rand() % nUniqueDataSize;

		m_vCenters[i] = uniqueDataSet.Get(nDataIndex);
		selectedIndexes.insert(nDataIndex);
	}
	return 0;
}

int CMLClustering_KMeans::ConvergeAllPoints(const CMLDataSet& dataSet, std::vector<std::vector<int>>& vClusters)
{
	IMLDataPointDistanceFunc* distFunc = GetDistanceFunc();
	std::vector<double> vKDists;
	vKDists.resize(m_nK, 0.0);
	vClusters.resize(m_nK);
	
	int i;
	int nClusterIndex;
	double minDist;
	int nMinDistClusterIndex;
	for (i=0; i<dataSet.Count(); i++)
	{
		const CMLDataPoint& dataPoint = dataSet.Get(i);
		// Find the minimum distance center
		minDist = DBL_MAX;
		nMinDistClusterIndex = -1;
		for (nClusterIndex=0; nClusterIndex<m_nK; nClusterIndex++)
		{
			double dDist = distFunc->Distance(dataPoint, m_vCenters[nClusterIndex]);
			if (dDist < minDist)
			{
				minDist = dDist;
				nMinDistClusterIndex = nClusterIndex;
			}
		}
		// Put the data to the cluster
		vClusters[nMinDistClusterIndex].push_back(i);
	}

	return 0;
}

int CMLClustering_KMeans::ResetCenters(const CMLDataSet& dataSet, std::vector<std::vector<int>>& vClusters)
{
	int nClusterIndex;
	if (dataSet.Count() == 0)
		return 0;

	int nDataPointSize = dataSet.Get(0).size();
	for (nClusterIndex=0; nClusterIndex<(int)vClusters.size(); nClusterIndex++)
	{
		int i;
		const std::vector<int>& vDataIndexes = vClusters[nClusterIndex]; 
		// Create the center point
		CMLDataPoint center(nDataPointSize);
		center.zero();
		// Calculate the sum
		for (i=0; i<(int)vDataIndexes.size(); i++)
			center.add(dataSet.Get(vDataIndexes[i]));
		// Get the mean
		center.div((int)vDataIndexes.size());
		// Reset the mean of clusters
		m_vCenters[nClusterIndex] = center;
	}

	return 0;
}

int CMLClustering_KMeans::ResetCentersWithWeights(const CMLDataSet& dataSet, const std::vector<double>& vWeights, 
													 std::vector<std::vector<int>>& vClusters)
{
	int nClusterIndex;
	if (dataSet.Count() == 0)
		return 0;

	int nDataPointSize = dataSet.Get(0).size();
	for (nClusterIndex=0; nClusterIndex<(int)vClusters.size(); nClusterIndex++)
	{
		int i;
		const std::vector<int>& vDataIndexes = vClusters[nClusterIndex]; 
		// Calculate totoal weights
		double dTotalWeights = 0;
		for (i=0; i<(int)vDataIndexes.size(); i++)
		{
			dTotalWeights += vWeights[vDataIndexes[i]];
		}
		// Create the center point
		CMLDataPoint center(nDataPointSize);
		center.zero();
		// Calculate the sum
		for (i=0; i<(int)vDataIndexes.size(); i++)
		{
			CMLDataPoint weightedPoint = dataSet.Get(vDataIndexes[i]);
			weightedPoint.mul(vWeights[vDataIndexes[i]] / dTotalWeights);
			center.add(weightedPoint);
		}
		// Reset the center of clusters
		m_vCenters[nClusterIndex] = center;
	}

	return 0;
}

bool CMLClustering_KMeans::IsClutersDifferent(const std::vector<std::vector<int>>& vClusters1, std::vector<std::vector<int>>& vClusters2)
{
	if (vClusters1.size() != vClusters2.size())
		return true;
	int i;
	int j;
	for (i=0; i<(int)vClusters1.size(); i++)
	{
		const std::vector<int>& vPointSet1 = vClusters1[i];
		const std::vector<int>& vPointSet2 = vClusters2[i];
		if (vPointSet1.size() != vPointSet2.size())
			return true;
		for (j=0; j<(int)vPointSet1.size(); j++)
		{
			if (vPointSet1[j] != vPointSet2[j])
				return true;
		}
	}
	return false;
}



_MYLABLIB_END
